package com.lihepeng.leecode.array2;

/**
 *
 *给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * @see Solution11
 */
public class Solution42 {
    /**
     * 使用双指针来实现
     * @param height
     * @return
     */
    int trap(int[] height){
        int left =0;
        int right = height.length-1;
        int l_max =0;
        int r_max =0;
        int ans =0 ;
        while (left<right) {
            l_max = Math.max(l_max,height[left]);
            r_max = Math.max(r_max,height[right]);
            if (l_max < r_max) {
                ans += l_max - height[left];
                left++;
            }else {
                ans+= r_max - height[right];
                right --;
            }
        }
        return ans;
    }

    /**
     * 使用动态规划的方案来实现
     * 完整学习完成之后再来查看
     * @param height
     * @return
     */
    public int trap1(int[] height) {
        return 0;
    }
}
